package hash;

import java.util.ArrayList;
import java.util.Arrays;

public class D230727 {
    // 三数之和
    // 固定一个数，然后使用双指针来找两数之和
    // 跳过重复的数来去重
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        int n = num.length;
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 固定下一个数时, 跳过重复的数
            while (i > 0 && i < n && num[i] == num[i - 1]) {
                i++;
            }
            if (i >= n || num[i] > 0) {
                // 小优化: 固定的这个数必须小于零(数组有序), 后面的数加起来才能等于零
                break;
            }
            // 双指针算法
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                if (sum == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    ret.add(list);
                    // 找到一种结果之后, 缩小区间继续寻找
                    // 跳过重复的数进行去重
                    do {
                        left++;
                    } while (left < right && num[left] == num[left - 1]);
                    do {
                        right--;
                    } while (left < right && num[right] == num[right + 1]);
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}
